package com.leetcode.tanxin;

import java.util.Arrays;
import java.util.Collection;
import java.util.stream.IntStream;

/**
 * 1005. K 次取反后最大化的数组和
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 * 示例 1：
 * 输入：nums = [4,2,3], k = 1
 * 输出：5
 * 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 * 示例 2：
 * 输入：nums = [3,-1,0,2], k = 3
 * 输出：6
 * 解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
 * 示例 3：
 * 输入：nums = [2,-3,-1,5,-4], k = 2
 * 输出：13
 * 解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
 * 提示：
 * 1 <= nums.length <= 104
 * -100 <= nums[i] <= 100
 * 1 <= k <= 104
 */
class Code1005 {
    public static void main(String[] args) {
        int[] nums = new int[]{4,4,-9,2,1,7,5,8};
        int k = 3;
        Code1005 code07 = new Code1005();
        int res = code07.largestSumAfterKNegations(nums,k);
        System.out.println(res);
    }
    public int largestSumAfterKNegations1(int[] nums, int k) {
        Arrays.sort(nums);
        if(nums[0] == 0){
            return add(nums);
        }
        if(nums[0]>0){
            return k%2==0 ? add(nums) : add(nums) - nums[0]*2;
        }
        if(nums[nums.length-1] < 0){
            if(nums.length <= k){
                for(int i = 0;i<nums.length;i++){
                    nums[i] = nums[i] * -1;
                }
                k = k - nums.length;
                nums[nums.length-1] = k>=2 && k%2==0?nums[nums.length-1]:nums[nums.length-1]*-1;
            }else {
                for(int i = 0;i<k;i++){
                    nums[i] = nums[i] * -1;
                }
            }
            return add(nums);
        }
        int index = 0;
        while(nums[index] < 0){
            index++;
        }
        if(index >= k){
            for(int i = 0;i<k;i++){
                nums[i] = nums[i] * -1;
            }
        }else {
            for(int i = 0;i<index;i++){
                nums[i] = nums[i] * -1;
            }
            if(nums[index] != 0){
                int temp = k - index;
                if(nums[index] > nums[index-1]){
                    nums[index-1] = temp>=2 && temp%2 == 0 ? nums[index-1] : nums[index-1] * -1;
                }else{
                    nums[index] = temp>=2 && temp%2 == 0 ? nums[index] : nums[index] * -1;
                }
            }
        }
        return add(nums);
    }
    public int add(int[] nums){
        int res = 0;
        for(int i = 0;i<nums.length;i++){
            res+=nums[i];
        }
        return res;
    }

    public int largestSumAfterKNegations(int[] nums, int K) {
        // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            //从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && K > 0) {
                nums[i] = -nums[i];
                K--;
            }
        }
        // 如果K还大于0，那么反复转变数值最小的元素，将K用完
        if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
        return Arrays.stream(nums).sum();
    }
}
